{\rtf1\ansi\deff3\adeflang1025
{\fonttbl{\f0\froman\fprq2\fcharset0 Times New Roman;}{\f1\froman\fprq2\fcharset2 Symbol;}{\f2\fswiss\fprq2\fcharset0 Arial;}{\f3\froman\fprq2\fcharset238 Times New Roman;}{\f4\fswiss\fprq2\fcharset238 Arial;}{\f5\froman\fprq0\fcharset128 Times New Roman;}{\f6\fnil\fprq0\fcharset238 sans-serif{\*\falt Arial};}{\f7\froman\fprq2\fcharset128 Times New Roman;}{\f8\fswiss\fprq2\fcharset238 Andale Sans UI{\*\falt Arial Unicode MS};}{\f9\fswiss\fprq2\fcharset238 Tahoma;}{\f10\fswiss\fprq0\fcharset238 Tahoma;}}
{\colortbl;\red0\green0\blue0;\red0\green0\blue128;\red128\green128\blue128;}
{\stylesheet{\s0\snext0\ql{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\ltrpar\nowidctlpar\cf0\kerning1\hich\af8\langfe255\dbch\af9\afs24\lang1081\loch\f3\fs24\lang255 Normal;}
{\*\cs15\snext15\cf2\ul\ulc0\langfe255\lang255 Internet Link;}
{\s16\sbasedon0\snext17\ql{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\sb240\sa120\keepn\ltrpar\cf0\kerning1\hich\af8\langfe255\dbch\af9\loch\f4\fs28\lang255 Heading;}
{\s17\sbasedon0\snext17\ql{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\sb0\sa120\ltrpar\cf0\kerning1\hich\af3\langfe255\dbch\af3\loch\f3\fs24\lang255 Text body;}
{\s18\sbasedon17\snext18\ql{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\sb0\sa120\ltrpar\cf0\kerning1\hich\af3\langfe255\dbch\af10\loch\f3\fs24\lang255 List;}
{\s19\sbasedon0\snext19\ql{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\sb120\sa120\ltrpar\cf0\i\kerning1\hich\af3\langfe255\dbch\af10\ai\loch\f3\fs24\lang255 Caption;}
{\s20\sbasedon0\snext20\ql{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\ltrpar\cf0\kerning1\hich\af3\langfe255\dbch\af10\loch\f3\fs24\lang255 Index;}
}{\info{\creatim\yr2009\mo4\dy16\hr11\min32}{\revtim\yr2011\mo11\dy2\hr1\min22}{\printim\yr0\mo0\dy0\hr0\min0}{\comment LibreOffice}{\vern3400}}\deftab706\deftab706\deftab706\deftab706\deftab706\deftab706\deftab706\deftab706\deftab706\deftab706\deftab706\deftab706\deftab706\deftab706\deftab706\deftab706\deftab706\deftab706\deftab706\deftab706

{\*\pgdsctbl
{\pgdsc0\pgdscuse195\pgwsxn11905\pghsxn16837\marglsxn1134\margrsxn1134\margtsxn1134\margbsxn1134\pgdscnxt0 Default;}}
\formshade{\*\pgdscno0}\paperh16837\paperw11905\margl1134\margr1134\margt1134\margb1134\sectd\sbknone\sectunlocked1\pgndec\pgwsxn11905\pghsxn16837\marglsxn1134\margrsxn1134\margtsxn1134\margbsxn1134\ftnbj\ftnstart1\ftnrstcont\ftnnar\aenddoc\aftnrstcont\aftnstart1\aftnnrlc
\pgndec\pard\plain \s0\ql{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\ltrpar\nowidctlpar\cf0\kerning1\hich\af8\langfe255\dbch\af9\afs24\lang1081\loch\f3\fs24\lang255\qc{\i0\b\afs28\ai0\ab\rtlch \ltrch\loch\fs28
Increasing power of LL(k) parsers}
\par \pard\plain \s0\ql{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\ltrpar\nowidctlpar\cf0\kerning1\hich\af8\langfe255\dbch\af9\afs24\lang1081\loch\f3\fs24\lang255\qc{\i\ai\rtlch \ltrch\loch\lang1051
by }{\i\ai\rtlch \ltrch\loch\lang1033
Jozef}{\i\ai\rtlch \ltrch\loch
 Lang(xlangj01), }{\i\ai\rtlch \ltrch\loch\lang1051
Zolt\'e1n }{\i\ai\rtlch \ltrch\loch\lang1031
Zemko(}{\i\ai\rtlch \ltrch\loch\lang1033
xzemko01)}
\par \pard\plain \s0\ql{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\ltrpar\nowidctlpar\cf0\kerning1\hich\af8\langfe255\dbch\af9\afs24\lang1081\loch\f3\fs24\lang255\qc{\i\ai\rtlch \ltrch\loch
Fakulta informa}{\i\ai\rtlch \ltrch\loch\lang1051
\'e8n\'edch technol\'f3gi\'ed}
\par \pard\plain \s0\ql{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\ltrpar\nowidctlpar\cf0\kerning1\hich\af8\langfe255\dbch\af9\afs24\lang1081\loch\f3\fs24\lang255\qc{\i\ai\rtlch \ltrch\loch\lang1051
Vysok\'e9 U\'e8en\'ed Technick\'e9 v Brn\'ec}
\par \pard\plain \s0\ql{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\ltrpar\nowidctlpar\cf0\kerning1\hich\af8\langfe255\dbch\af9\afs24\lang1081\loch\f3\fs24\lang255\qc{\i\ai\rtlch \ltrch\lang1051
2011}
\par \pard\plain \s0\ql{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\ltrpar\nowidctlpar\cf0\kerning1\hich\af8\langfe255\dbch\af9\afs24\lang1081\loch\f3\fs24\lang255\qc{\rtlch \ltrch\loch
}
\par \pard\plain \s0\ql{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\ltrpar\nowidctlpar\cf0\kerning1\hich\af8\langfe255\dbch\af9\afs24\lang1081\loch\f3\fs24\lang255\qj{\b\ab\rtlch \ltrch\loch\lang1033
Abstract:}
\par \pard\plain \s0\ql{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\ltrpar\nowidctlpar\cf0\kerning1\hich\af8\langfe255\dbch\af9\afs24\lang1081\loch\f3\fs24\lang255\qc{\rtlch \ltrch\loch
}
\par \pard\plain \s0\ql{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\ltrpar\nowidctlpar\cf0\kerning1\hich\af8\langfe255\dbch\af9\afs24\lang1081\loch\f3\fs24\lang255\qj{\b\ab\rtlch \ltrch\loch\lang1033
Motivation }{\rtlch \ltrch\loch\lang1033
Non-deterministic top-down parsers are not efficient. They must find first derivation to proceed. Deterministic top-down parsers are faster, because ambiguity is no longer a problem. LL(1) parsers are quite efficient, but there are occasionally situations when LL(1) parsers are not useful and it is better to look ahead }{\i\ai\rtlch \ltrch\loch\lang1033
k }{\rtlch \ltrch\loch\lang1033
symbols with }{\i\ai\rtlch \ltrch\loch\lang1033
k > 1. }{\rtlch \ltrch\loch\lang1033
Here it comes to construction of LL(k) parsers that brings up new problems.}
\par \pard\plain \s0\ql{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\ltrpar\nowidctlpar\cf0\kerning1\hich\af8\langfe255\dbch\af9\afs24\lang1081\loch\f3\fs24\lang255\qj{\rtlch \ltrch\loch
}
\par \pard\plain \s0\ql{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\ltrpar\nowidctlpar\cf0\kerning1\hich\af8\langfe255\dbch\af9\afs24\lang1081\loch\f3\fs24\lang255\qj{\b\ab\rtlch \ltrch\loch\lang1033
Problem statement }{\rtlch \ltrch\loch\lang1033
For every LL(k) grammar there are LL(k+1) grammars that are not LL(k). With LL(k) grammars the same problems must be solved as with LL(1) grammars; producing parse table is difficult. In LL(1) grammars we can tell whether the grammar is strong-LL(1) and thus LL(1) just by taking first and follow sets. In LL(k) grammars this does not hold, when a grammar is LL(k) it does not imply that it is also a strong-LL(k) grammar. Another disadvantage of LL(k) parser is the size of parse tables. Parse tables of LL(k) grammars are big, but cells are only seldom occupied and thus parsing tables are suitable to table compression. }
\par \pard\plain \s0\ql{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\ltrpar\nowidctlpar\cf0\kerning1\hich\af8\langfe255\dbch\af9\afs24\lang1081\loch\f3\fs24\lang255\qj{\rtlch \ltrch\loch\lang1033
Second problem discussed; LL(k) grammars provide bounded-look ahead and this is not always sufficient, because discriminating token can be arbitrary far away. }
\par \pard\plain \s0\ql{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\ltrpar\nowidctlpar\cf0\kerning1\hich\af8\langfe255\dbch\af9\afs24\lang1081\loch\f3\fs24\lang255\qj{\rtlch \ltrch\loch\lang1033
Third problem discussed are extended LL(1) grammars. Several parser generators accept extended context-free grammars and thus these must be transformed into ordinary one without introducing LL(1) conflicts.}
\par \pard\plain \s0\ql{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\ltrpar\nowidctlpar\cf0\kerning1\hich\af8\langfe255\dbch\af9\afs24\lang1081\loch\f3\fs24\lang255\qj{\rtlch \ltrch\loch
}
\par \pard\plain \s0\ql{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\ltrpar\nowidctlpar\cf0\kerning1\hich\af8\langfe255\dbch\af9\afs24\lang1081\loch\f3\fs24\lang255\qj{\b\ab\rtlch \ltrch\loch\lang1033
Results }{\rtlch \ltrch\loch\lang1033
The problem of the size of LL(k) parsing tables can be avoided by a simple trick; in addition to first, second, third sets etc can be computed. This adjustment transforms the size of the parse table from O(t}{{\*\updnprop10000}\up10\rtlch \ltrch\loch\lang1033
2}{\rtlch \ltrch\loch\lang1033
) to O(t) and table is not only smaller, but also easier to generate. This types of grammars are called }{\i\ai\rtlch \ltrch\loch\lang1033
Linear-approximate LL(k) }{\rtlch \ltrch\loch\lang1033
grammars.}
\par \pard\plain \s0\ql{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\ltrpar\nowidctlpar\cf0\kerning1\hich\af8\langfe255\dbch\af9\afs24\lang1081\loch\f3\fs24\lang255\qj{\rtlch \ltrch\loch\lang1033
The solution to the second discussed problem is to use unbounded-look ahead, but this brings up new problems; they can be solved by approximation CF grammar by regular grammar, where problems brought up by unbounded-look ahead are easily solved. This type of grammars are called }{\i\ai\rtlch \ltrch\loch\lang1033
LL-regular }{\rtlch \ltrch\loch\lang1033
grammars due to approximation by the regular grammars.}
\par \pard\plain \s0\ql{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\ltrpar\nowidctlpar\cf0\kerning1\hich\af8\langfe255\dbch\af9\afs24\lang1081\loch\f3\fs24\lang255\qj{\rtlch \ltrch\loch\lang1033
Extended parsers work in the following way. Firstly parser transforms extended grammar to an ordinary one and then produces parse table for it. It holds that if resulting context-free grammar is LL(1) then original grammar is ELL(1) (Extended LL(1)). }
\par \pard\plain \s0\ql{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\ltrpar\nowidctlpar\cf0\kerning1\hich\af8\langfe255\dbch\af9\afs24\lang1081\loch\f3\fs24\lang255\qj{\rtlch \ltrch\loch
}
\par \pard\plain \s0\ql{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\ltrpar\nowidctlpar\cf0\kerning1\hich\af8\langfe255\dbch\af9\afs24\lang1081\loch\f3\fs24\lang255\qj{\b\ab\rtlch \ltrch\loch\lang1033
Conclusion }{\rtlch \ltrch\loch\lang1033
LL(1) parsers are very intuitive, they read input from left to right looking forward only one symbol. But there are situations where LL(k) grammars are not very useful, especially when  grammar can contains }{\scaps0\caps0\cf1\expnd0\expndtw0\i0\b0\afs24\ab0\rtlch \ltrch\loch\fs24\lang1032\loch\f7
\u949\'3f}{\rtlch \ltrch\loch\lang1033
 symbol,. The use of LL(k) grammars brings up new problems, some as }{\i\ai\rtlch \ltrch\loch\lang1033
LL-regular grammars}{\rtlch \ltrch\loch\lang1033
 are rather the problems in theoretical point of view and in real world are seldom used. Other problems find its application in the real world.}
\par \pard\plain \s0\ql{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\ltrpar\nowidctlpar\cf0\kerning1\hich\af8\langfe255\dbch\af9\afs24\lang1081\loch\f3\fs24\lang255\qj{\rtlch \ltrch\loch
}
\par \pard\plain \s0\ql{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\ltrpar\nowidctlpar\cf0\kerning1\hich\af8\langfe255\dbch\af9\afs24\lang1081\loch\f3\fs24\lang255\qj{\b\ab\rtlch \ltrch\loch\lang1033
Bibliography:}
\par \pard\plain \s0\ql{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\ltrpar\nowidctlpar\cf0\kerning1\hich\af8\langfe255\dbch\af9\afs24\lang1081\loch\f3\fs24\lang255\qj{\rtlch \ltrch\loch\lang1033
Grune, D., Jacobs, C.J.H.: Parsing Techniques: A Practical Guide (2nd Edition). Springer, 2008, ISBN 978-0-387-20248-8. Chapter 8.}
\par }